

/*
 * myRBMap.h
 * 红黑树 map
 * westice 2012-8-31
 */

#include "myTools.h"
 
#pragma once              //防止头文件被多次包含

typedef enum myRBNodeColorType{
	myRBNodeRed,
	myRBNodeBlack,
	colorNoDefine
}myRBNodeColor;

typedef enum myRBNodeLRonPType{
	myRBNodeLeft,
	myRBNodeRight,
	lrNoDefine
}myRBNodeLRonP;
 
typedef struct myRBMapNodeType{
	struct myRBMapNodeType* parentNode;
	struct myRBMapNodeType* leftSonNode;
	struct myRBMapNodeType* rightSonNode;
	myRBNodeLRonP nodeLRonP;  //为父亲的左或右
	myRBNodeColor nodeColor;
	int nodeInvalid;          //标志节点是否有效
	//这里采用预删除机制，删除时标志节点无效，但是参与树的构成，当有个相同的key插入时复用这个节点
	
	int iKey;
	int testValue;
	void* bindDataPtr;
}myRBMapNode; 

typedef struct myRBMapType{
	myRBMapNode* rootNode;
	int nodeCount;
}myRBMap;

myRBMapNode getNullNode(int key,int v);

myRBMap* createMyRBMap();
void releaseMyRBMap(myRBMap* rbMap);  //释放全部内存

void myRBMapAddItem(myRBMap* rbMap,myRBMapNode* node);
myRBMapNode* myRBMapFindItemWithiKey(myRBMap* rbMap,int iKey);
void myRBMapRemoveItem(myRBMap* rbMap);    //预删除节点，不释放内存
void myRBMapRleaseInvalidItem(myRBMap* rbMap);  //删除无效节点，并释放内存
void myRBMapRemoveAll(myRBMap* rbMap);     //预删除所有节点，不释放内存


void printMyRBMapMidOrder(myRBMap* rbMap);  // 中序输出 红黑树


